import sun.java2d.pipe.AAShapePipe;

import java.util.*;

class Student {
    public String id;

    public Student(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class test {
    public List<String> topKFrequent(String[] words, int k) {
        //是否还记得求前K个最小元素
        //这一题也是利用之前的思路来完成
        //1.先统计每个单词出现的次数
        //2.这里是求最大，所以建立小根堆

        //1.统计次数
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }

        //2.遍历map,构建小堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //return o1.getValue() - o2.getValue();
                //或者
                //return o1.getValue().compareTo(o2.getValue());
                //这里存在问题，当放入元素频率相同时，我们需要转变为大根堆
                //这样最后逆置就不会出现问题
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        //小根堆中存放的元素是一个map中存放的元素，包括 key 和 val
        //并且要传入比较器

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
                //此时小根堆中数量小于k，所以要往里面添加元素
            } else {
                //此时找最大频率单词，就是遇到比堆顶元素大的就先删除栈顶元素，之后入堆
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    //因为可能有相同频率单词，所以这里需要考虑情况
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            //此时按照字典序排序
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        //此时已经全部放入小根堆 eg: 2 3 4
        //最终返回结果为List
        List<String> list = new ArrayList<>();
        //将minHeap中的元素逐个放入list中
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            list.add(top.getKey());
        }

        //此时就需要逆置了
        Collections.reverse(list);
        return list;
    }

    public static void main7(String[] args) {
        int[] arr = {1, 2, 3, 3, 2};
        PriorityQueue<Integer> p = new PriorityQueue<>();

        HashMap<Integer, Integer> map = new HashMap<>();
        for (Integer x : arr) {
            if (map.get(x) == null) {
                //第一次存放
                map.put(x, 1);
            } else {
                //其他情况在原来的基础上加 1
                int val = map.get(x);
                map.put(x, val + 1);
            }
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println("key: " + entry.getKey() + " val: " + entry.getValue());
        }
    }
    public static void main6(String[] args) {
        int[] num = {4, 1, 2, 1, 2};
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            if (hashSet.isEmpty() || !hashSet.contains(num[i])) {
                hashSet.add(num[i]);
            } else {
                hashSet.remove(num[i]);
            }
        }

        HashMap<Integer,Integer> map = new HashMap<>();

        System.out.println(hashSet);


    }
    public static void main5(String[] args) {
        Student student1 = new Student("613");
        Student student2 = new Student("613");

        HashBuck<Student, Integer> hashBuck = new HashBuck<>();
        hashBuck.put(student1, 10);
        System.out.println(hashBuck.getValue(student2));
    }
    public static void main4(String[] args) {
        Student student1 = new Student("613");
        Student student2 = new Student("613");

        System.out.println(student1.hashCode());// x % len （x 是hashCode的结果）
        System.out.println(student2.hashCode());

        HashMap<Student, Integer> map = new HashMap<>();
        map.put(student1, 2);

        System.out.println(map.get(student2));//并没有放入student2

    }

    public static void main3(String[] args) {
        //set不能存储相同的key 可以去重
        HashSet<String> set = new HashSet<>();
        set.add("hello");
        set.add("abcd");
        set.add("hello");

        System.out.println(set);
    }
    public static void main2(String[] args) {
//        HashMap<Student, Integer> map = new HashMap<>();
//        map.put(new Student(), 2);
//        map.put(new Student(), 2);
//        //这里的Student里面没有任何内容
//        map.put(null, 2);
    }

    public static void main1(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("abcd", 2);
        map.put("hello", 10);
        map.put("gao", 3);

        Integer val = map.get("abcd");
        System.out.println(val);

        System.out.println(map);

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("key: " + entry.getKey() + " val: " + entry.getValue());
        }
        //不支持迭代器遍历
    }

}
